package com.zwj.interview.BFS;

import java.util.Stack;

/**
 * @Author: Zwj
 * @Date: 2023/2/13 19:50
 */
public class 二叉树变双链表 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;
        //设置栈用于遍历
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode head = null;
        TreeNode pre = null;
        TreeNode cur=pRootOfTree;
        //确认第一个遍历到最左，即为首位
        boolean isFirst = true;
        while(cur != null || !s.isEmpty()){
            //直到没有左节点
            while(cur != null){
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            //最左元素即表头
            if(isFirst){
                head = cur;
                pre = head;
                isFirst = false;
                //当前节点与上一节点建立连接，将pre设置为当前值
            }else{
                //这里就是维护双向链表关系
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            //根节点往右边走
            cur = cur.right;
        }
        return head;
    }
}